uva 10881

ACM
评论

长度为L的线段上有n只蚂蚁，它们如果相遇就反转方向，如果走出线段外就fell off。给出每个蚂蚁的初始位置和朝向，问时间T后每个蚂蚁的位置和朝向。

性质一：每两个蚂蚁相遇之后，相当于交换它们的标号，行动轨迹不变。
性质二：蚂蚁和蚂蚁之间的相对位置始终不变。
所以先处理每个蚂蚁的位置，再判断最终位置是否在线段上就成。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <cstdio>
#include <cmath>
#include <cstring>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 10000000
#define debug puts("-----")
#define maxn 10000+6
#define NV 1000
#define NE 10000
#define LL long long
int a[maxn],b[maxn];
int r[maxn],rk[maxn];
//有起始点相同的蚂蚁就GG
int cmp(int x,int y)
{
	return a[x]<a[y];
}
int main()
{
	int t;
	scanf("%d",&t);
	int cas=0;
	while(t--)
	{
		int l,T,n;
		scanf("%d%d%d",&l,&T,&n);
		for(int i=0;i<n;i++)
		{
			char w;
			scanf("%d %c",&a[i],&w);
			if(w=='R')b[i]=1;
			else b[i]=0;
			r[i]=i;
		}
		sort(r,r+n,cmp);
		for(int i=0;i<n;i++)
			rk[r[i]]=i;
		for(int i=0;i<n;i++)
		{
			if(b[i])a[i]+=T;
			else a[i]-=T;
			r[i]=i;
		}
		sort(r,r+n,cmp);
		for(int i=1;i<n;i++)
			if(a[r[i]]==a[r[i-1]])b[r[i]]=b[r[i-1]]=2;
		printf("Case #%d:\n",++cas);
		for(int i=0;i<n;i++)
		{
			int e=r[rk[i]];
			if(a[e]<0||a[e]>l)
				puts("Fell off");
			else 
			{
				printf("%d ",a[e]);
					if(b[e]==2)
					puts("Turning");
					else if(b[e]==1)puts("R");
					else puts("L");
			}
		}
		puts("");
	}
}

EOF